package com.power.algorithm.test;

import java.util.Arrays;

/**
 * @description:
 * @author: jiangnan
 * @time: 2021/6/21 1:53 下午
 */
public class KMP {
    // 获取字符串的部分匹配值
    public static int[] MatchValue(String str2) {
        // 创建数组保存数据
        int[] next = new int[str2.length()];
        next[0] = 0;// 字符串的长度为1,部分匹配值就是0

        for (int i = 1, j = 0; i < next.length; i++) {
            while (str2.charAt(i) != str2.charAt(j) && j > 0) {
                j = next[j - 1];
            }

            if (str2.charAt(i) == str2.charAt(j)) { // 部分匹配值加一
                j++;
            }
            next[i] = j;
        }
        return next;
    }

    // 查找算法
    public static int KMPsearch(String str1, String str2, int[] next) {
        // 遍历str1
        for (int i = 0, j = 0; i < str1.length(); i++) {
            while (j > 0 && str1.charAt(i) != str2.charAt(j)) {
                j = next[j - 1];
            }
            if (str1.charAt(i) == str2.charAt(j)) {
                j++;
            }
            if (j == str2.length()) {
                return i - j + 1;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        String str1 = "ABCDAB ABCDABABCDABDEA";
        String str2 = "ABCDABD";
        int[] next = MatchValue(str2);
        System.out.println("next = " + Arrays.toString(next));
        int index = KMPsearch(str1, str2, next);
        System.out.println("index = " + index);
    }
}
